# 398 中等：随机数索引
import random
from collections import defaultdict


class Solution:

    # def __init__(self, nums: List[int]):
    # 哈希表
    # def __init__(self, nums):
    #     self.dict = defaultdict(list)
    #     for i in range(len(nums)):
    #         self.dict[nums[i]].append(i)
    #
    # def pick(self, target: int) -> int:
    #     return random.choice(self.dict[target])

    # 水塘抽样  等概率选取一个目标
    def __init__(self, nums):
        self.nums = nums

    def pick(self, target):
        cnt = 0
        ret = -1
        for i in range(len(self.nums)):
            if self.nums[i] == target:
                if random.randint(0, cnt) == 0:
                    ret = i
                cnt += 1

        return ret







# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)
